Graph / Spanning subgraph (Bibtex)

P138: Enumeration of all minimal $k$-vertex connected spanning subgraphs in a $k$-connected graph.

Input:

A $k$-connected graph $G$.

Output:

All minimal $k$-vertex connected spanning subgraphs in $G$.

Complexity:

$O(K^3|E|^3|n| + K^2|E|^5|V|^4 + K|V|^k|E|^2)$ total time.

Comment:

$K$ is the number of solutions. A graph $G$ is $k$-connected if a subgraph of $G$ obtained by removing at most $k-1$ vertices is still connected.

Reference:

[Boros2007] (Bibtex)

P234: Enumeration of all minimal spanning graph

Input:

A graph $G = (V, E)$, $S \subseteq V$, and requirements $r(u, v)$ for all $(u, v) \in V \times V$.

Output:

All minimal spanning graph $H$ of $G$ satisfying $\lambda^S_H \ge r(u, v) \; \forall (u, v) \in V \times V$.

Complexity:

Incremental polynomial time.

Comment:

The $S$-connectivity $\lambda^S_G(u, v)$ of $(u, v)$ in $G$ is the maximum number of $uv$-paths such that no two of them have an edge or a node in $S \setminus \{u, v\}$ in common. This complexity holds for edge-connectivity.

Reference:

[Nutov2009] (Bibtex)

P235: Enumeration of all $k$-outconnected minimal spanning graph

Input:

A graph $G = (V, E)$, a vertex $s \in V$, and an integer $k$.

Output:

All minimal $k$-outconneted from $s$ spanning subgraph of $G$.

Complexity:

Incremental polynomial time.

Comment:

A graph is $k$-outconnected from $s$ if it contains $k$ internally-disjoint $st$-paths for every $t \in V$. This complexity holds for both vertex and edge-connectivity.

Reference:

[Nutov2009] (Bibtex)

P236: Enumeration of all $k$-outconnected minimal spanning graph

Input:

A directed graph $G = (V, E)$, a vertex $s \in V$, and an integer $k$.

Output:

All minimal $k$-outconneted from $s$ spanning subgraph of $G$.

Complexity:

Incremental polynomial time.

Comment:

A graph is $k$-outconnected from $s$ if it contains $k$ internally-disjoint $st$-paths for every $t \in V$. This complexity holds for both vertex and edge-connectivity.

Reference:

[Nutov2009] (Bibtex)

P237: Enumeration of all $k$-connected minimal spanning graph

Input:

A directed graph $G = (V, E)$ and an integer $k$.

Output:

All minimal $k$-connected spanning subgraph of $G$.

Complexity:

Incremental polynomial time.

Comment:

This complexity holds for both vertex and edge-connectivity.

Reference:

[Nutov2009] (Bibtex)